//
// Created by xili on 2024/8/28 15:25.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//全部异或
class Solution1 {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int ans = 0;
        for (auto &item: nums) {
            ans ^= item;
        }
        return ans;
    }
};

//二分查找
class Solution2 {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
};
